Ở Red Medicine, Fugazi bắt đầu thử sức với những thế loại âm nhạc mới lạ hơn với họ, như noise punk, psychedelia ("By You") và dub ("Version").[3]

Ban nhạc bắt đầu sáng tác Red Medicine năm 1994, sau thời gian khi lưu diễn quảng bá In on the Kill Taker. Tiến trình sáng tác cho album gồm nhiều tháng jam và thu âm tại Guilford House, Guilford, Connecticut.

Quá trình thu chỉ kéo dài hai tháng vào tháng 1 và tháng 2, năm 1995 tại Inner Ear Studios ở Arlington, VA. Họ làm việc với kỹ thuật viên Don Zientara, và không tiếp tục hợp tác với nhà sản xuất Ted Niceley nữa. Fugazi quyết định từ bỏ kiểu sản xuất in-your-face của In on the Kill Taker, thay vào đó cố tạo nên một âm thanh "ambient" hơn. Để đạt được điều đó, họ tự mình sản xuất album, và nhờ vậy, tự tin hơn với sự thử nghiệm trong phòng thu.[4]Tiến trình sáng tác và thu âm được quay lại và trở thành một phần của phim Instrument.